"""
    两个链表的第一个公共节点
"""


class ListNode:
    """节点类"""
    def __init__(self, val):
        self.val = val
        self.next = None


class Solution:
    def get_first_public_node(self, head1, head2):
        """
        判断是否为同一个对象: 类比 a is b
        :param head1:
        :param head2:
        :return: 第一个公共节点
        """
        list01 = []
        list02 = []

        while head1:
            list01.append(head1)
            head1 = head1.next

        while head2:
            list02.append(head2)
            head2 = head2.next

        # list01: [Node(1),Node(2),Node(3),Node(6),Node(7)]
        # list02: [Node(4),Node(5),Node(6),Node(7)]
        public_node = None
        while list01 and list02 and list01[-1] is list02[-1]:
            public_node = list01.pop()
            list02.pop()

        return public_node


if __name__ == '__main__':
    head1 = ListNode(1)
    head2 = ListNode(4)
    n2 = ListNode(2)
    n3 = ListNode(3)
    n5 = ListNode(5)
    n6 = ListNode(6)
    n7 = ListNode(7)
    # 链表1: 1 2 3 6 7
    head1.next = n2
    n2.next = n3
    n3.next = n6
    n6.next = n7
    # 链表2: 4 5 6 7
    head2.next = n5
    n5.next = n6
    n6.next = n7
    # 测试方法
    s = Solution()
    public_node = s.get_first_public_node(head1, head2)
    print(public_node.val)